#include<assert.h>
#include<iostream>
#include<initializer_list>
using namespace std;

//list的底层是:带头双向循环链表
namespace Mango
{
//节点设计
template<class T>
struct ListNode
{
  ListNode<T>* _prev;
  ListNode<T>* _next;
  T _val;
  ListNode(const T& val = T()) //节点的默认值为该类型对象的默认构造函数所生成的值
    :_val(val),_prev(nullptr),_next(nullptr)
  {}
};


//list的迭代器不是原生指针，而是对指针的封装
//vector和string的迭代器是原生指针，因为他们底层是连续的空间,所以对指针的++/--可以对相应位置进行操作
//而因为list的节点在内存当中的地址是随机的，所以不能直接通过对指针进行++/--对相应位置进行操作，所以可以对指针进行封装
//迭代器的意义：让使用者不用关心底层的结构，使用统一的方式对容器进行访问


//需要三个参数,为了更好的区分普通迭代器和const迭代器
//如果是const迭代器: Ref:const T&   Ptr: const T*
//如果是普通迭代器: Ref：T&     Ptr:T*
template<class T,class Ref,class Ptr>
struct List_Iterator 
{
  typedef ListNode<T> Node; //节点类型
  typedef List_Iterator<T,Ref,Ptr> self;//迭代器自身类型
  List_Iterator(Node* p) :pnode(p) 
  {}
  //关于拷贝构造函数/赋值重载函数:不需要我们实现,因为成员是内置类型，默认就是浅拷贝,而我们需要的也是浅拷贝,二者指向同一个节点
  //关于析构函数:节点的释放不归迭代器管,而归list管,迭代器只是为了更好的访问容器
  
  //为了让迭代器能像指针一样操作,所以要重载operator->  和 operator*
  //如果是const迭代器: Ref:const T&   Ptr: const T*
  //如果是普通迭代器: Ref：T&     Ptr:T*
  Ptr operator->()
  {
    return &pnode->_val; 
  }
  Ref operator*()
  {
    return pnode->_val;
  }
  //后置运算需要多增加一个int类型的参数用于区分前置还是后置运算
  //前置++/前置-- 返回的是迭代器的引用对象
  self& operator++()
  {
      pnode = pnode->_next;
      return *this;
  }
  self operator++(int) //后置++
  {
    self tmp(*this);//复用拷贝构造
    pnode = pnode->_next;
    return tmp;
  }
  self& operator--()
  {
    pnode = pnode->_prev;
    return *this;
  }
  self operator--(int)
  {
    self tmp(*this);
    pnode = pnode->_prev;
    return tmp;
  }
  //因为迭代器遍历的时候需要比较判断,所以要重载!= 和 == 
  bool operator!=(const self& it)
  {
    return pnode != it.pnode;
  }
  bool operator==(const self& it)
  {
    return pnode == it.pnode;
  }
  Node* pnode;//list的迭代器实际是对节点指针的封装
};

template<class T>
class list 
{
public:
  typedef ListNode<T> Node;
  typedef List_Iterator<T,T&,T*> iterator;
  typedef List_Iterator<T,const T&,const T*> const_iterator;
  //注意:凡是构造函数,都需要先创建一个哨兵位节点!!!!!!!!!!!!
 list()
 {
   CreateHead();
 }
 list(size_t n ,const T& val = T())
 {
   CreateHead();
   for(size_t i = 0;i<n;i++)
   {
     push_back(val);
   }
 }

 list(int n ,const T& val = T())
 {
   CreateHead();
   for(int i = 0;i<n;i++)
   {
     push_back(val);
   }
 }

 void swap(list<T>& lt) //交换两个list,本质就是把两个哨兵位节点指针进行交换即可
 {
   ::swap(lt._head,_head);
 }
  //传统写法:遍历lt的元素插入到list当中
 list(const initializer_list<T>& il)
 {
    CreateHead();
    auto it = il.begin();
    while(it != il.end())
    {
      push_back(*it);
      it++;
    }
 }
 //现代写法:复用迭代器构造
 //list(const initializer_list<T>& il)
 //{
 //   list<T> lt(il.begin(),il.end());
 //   swap(lt);
 //}
 
 template<class InputIterator>
 list(InputIterator first,InputIterator last)
 {
   CreateHead();
   while(first != last)
   {
     push_back(*first);
     first++;
   }
 }

 //传统写法: 遍历元素然后插入
 list(const list<T>& lt)
 {
    CreateHead();
    cout << "list(const lit<T>& lt)" << endl;   
    for(auto& x:lt)
    {
      push_back(x);
    }
 }
 //现代写法:直接构造一个临时对象然后交换
 //list(const list<T>& lt)
 //{
 //   cout <<"list(const list<T>& lt)" << endl;
 //   list<T> tmp(lt.begin(),lt.end());//复用迭代器构造
 //   swap(tmp);
 //}
 

 //传统写法
 list<T>& operator=(const list<T>& lt)
 {
  cout << "list<T>& operator=(const list<T>& lt)" << endl;
  if(this != &lt)
  {
    for(auto& x:lt)
    {
      push_back(x);
    }
  }
  return *this;
 }

 //现代写法:
 //list<T>& operator=(const list<T>& lt) 
 //{
 //   cout << "list<T>& operator=(const list<T>& lt)" << endl;
 //   if(this != &lt)
 //   {
 //     list<T> tmp(lt.begin(),lt.end()); 
 //     swap(tmp);
 //   }
 //   return *this;
 //}

 ~list()
 {
   clear();//释放除哨兵位外的节点
   //注意:要将哨兵位也释放,
   delete _head;
   _head = nullptr;
 }
 //因为节点都是new出来的,所以需要释放节点的内容
 void clear()
 {
   Node* cur = _head->_next;
   while(cur != _head)
   {
      Node* next = cur->_next; //保存下一个节点
      delete cur;
      cur = next;
   }
 }

 //迭代器
 iterator begin()
 {
    return iterator(_head->_next);
 }
 iterator end()
 {
    return iterator(_head);
 }
 const_iterator begin()  const
 {
    return const_iterator(_head->_next);
 }
 const_iterator end() const 
 {
    return const_iterator(_head);
 }
 
 //在pos位置前插入
 iterator insert(iterator pos,const T& val) //返回插入位置的迭代器
 {
    //pos迭代器中的结点指针不能为空
    assert(pos.pnode != nullptr);
    Node* cur = pos.pnode; 
    Node* prev = cur->_prev;
    Node* newnode = new Node(val);
    //prev newnode cur 
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
    
    return iterator(newnode);
 }
 iterator erase(iterator pos) //返回删除位置的下一个位置的迭代器
 {
    //防止删除的是哨兵位
    assert(pos.pnode != _head); //或者写成: assert(pos != end()) 
    //pos迭代器中的结点指针不能为空
    assert(pos.pnode != nullptr);

    Node* cur = pos.pnode;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
 }
 void push_back(const T& val)
 {
  insert(end(),val);
 }
 void pop_back()
 {
   iterator last = --end();
   erase(last);
 }
 void push_front(const T& val)
 {
    insert(begin(),val);
 }
 void pop_front()
 {
    erase(begin());
 }
 //方法1:遍历list统计节点个数
 //方法2:给list类增加一个成员size记录节点的个数
 size_t size() const 
 {
    size_t count = 0;
    auto it = begin();
    while(it != end())
    {
      count++;
      it++;
    }
    return count;
 }
 bool empty() const 
 {
   return _head->_next == _head;
 }
 void resize(size_t n,const T& val = T())
 {
    int oldsize = size(); // 5
    if(oldsize >= n) //说明要缩小元素个数:oldsize-n个
    {
      for(int i = 0;i<oldsize-n;i++)
      {
        pop_back();
      }
    }
    else  //增加元素个数 :n-oldsize个
    {
      for(int i = 0;i<n-oldsize;i++)
      {
        push_back(val);
      }
    }
 }
 
 T& front()
 {
  assert(!empty());
  return *begin();
 }
 T& back()
 {
   assert(!empty());
   return *(--end());
 }
 const T& front() const 
 {
  assert(!empty());
  return *begin();
 }
 const T& back() const 
 {
   assert(!empty());
   return *(--end());
 }
private:
  void CreateHead() //最初：哨兵位节点的前后指针指向自己
  {
    _head = new ListNode<T>();
    _head->_prev = _head;
    _head->_next = _head;
  }
  ListNode<T>* _head;//指向哨兵位节点
};

void test_list1()
{
    list<int> lt1{1,2,3,4,5};
    for(auto x:lt1)
      cout << x <<  " ";
    cout << endl;

    list<int> lt2 = lt1;
    for(auto x:lt2)
      cout << x <<  " ";
    cout << endl;

    list<int> lt3;
    lt3 = lt1;
    for(auto x:lt3)
      cout << x <<  " ";
    cout << endl;
}


void test_list2()
{
    list<int> lt1 = list<int>();
    lt1 = {1,2,3,4,5};
    for(auto x:lt1)
      cout << x <<  " ";
    cout << endl;

    lt1.resize(10,0);
     for(auto x:lt1)
      cout << x <<  " ";
    cout << endl;

    cout << lt1.front()<<endl;
    cout << lt1.back()<<endl;
}


}
